import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-04
 * Time: 23:37
 */
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        //直接先判断再往map里面放,可以直接避免了与自己匹配
        //同时减少代码量和时间复杂度
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }

    /**
     *  先固定一个数, 另一个数字用二分查找
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum2(int[] numbers, int target) {
        for (int i = 0;i < numbers.length && numbers[i] <= target / 2;i++) {
            int left = i + 1;
            int right = numbers.length - 1;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i, mid};
                }else if (numbers[mid] < target - numbers[i]) {
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    /**
     *  双指针
     *  sum > target right--
     *  sum < target left++
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum3(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left, right};
            }else if (sum < target) {
                left++;
            }else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}
